package medium;

import java.awt.image.AreaAveragingScaleFilter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 2192. 有向无环图中一个节点的所有祖先
 * 创建时间：2024-04-04 17:41
 * 地址：https://leetcode.cn/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/description/
 */
public class 有向无环图中一个节点的所有祖先_2192 {
    static class Solution {
        public List<List<Integer>> getAncestors(int n, int[][] edges) {
            List<Integer>[] g = new ArrayList[n];
            Arrays.setAll(g, i -> new ArrayList<>());
            for (int[] edge : edges) {
                g[edge[0]].add(edge[1]);
            }
            System.out.println(Arrays.asList(g));
            List<Integer>[] ans = new ArrayList[n];
            Arrays.setAll(ans, i -> new ArrayList<>());
            int[] isAdd = new int[n];
            Arrays.fill(isAdd, -1);
            // 遍历每个节点
            for (int start = 0; start < n; start++) {
                dfs(ans, g, isAdd, start, start);
                System.out.println(Arrays.asList(ans));
            }
            return Arrays.asList(ans);
        }

        private void dfs(List<Integer>[] ans, List<Integer>[] grap, int[] isAdd, int start, int index) {
            isAdd[index] = start;
            for (int g : grap[index]) {
                if (isAdd[g] != start) {
                    ans[g].add(start);
                    dfs(ans, grap, isAdd, start, g);
                }
            }
        }

        public static void main(String[] args) {
            Solution s = new Solution();
            int[][] arr = {{0, 3},{0,4},{1,3},{2,4},{2,7},{3,5},{3,6},{3,7},{4,6}};
            System.out.println(s.getAncestors(8, arr));
        }
    }
}
